import java.util.ArrayList;
import java.util.Collections;
import java.util.*;

public class 字母异位词分组 {
    public List<List<String>> groupAnagrams(String[] strs) {
        //建立一个哈希表来映射, 建立一个线性表来返回
        List<List<String>> ret = new ArrayList<>();
        Map<String,List<String>> map = new HashMap<>();
        //遍历每一个字符串
        for(int i = 0;i < strs.length;i++){
            //转成字符数组才可以用排序
            char[] s = strs[i].toCharArray();
            Arrays.sort(s);
            //转回字符串
            String str = new String(s);
            //不存在的话就创建一个表
            if(!map.containsKey(str)){
                List<String> cur = new ArrayList<>();
                cur.add(strs[i]);
                map.put(str,cur);
            }else{
                //存在直接加
                map.get(str).add(strs[i]);
            }
        }
        //全部倒出来放到ret里面
        for (Map.Entry<String,List<String>> entry : map.entrySet()) {
            ret.add(entry.getValue());
        }
        return ret;
    }

    //速度更快
    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(int i = 0;i < strs.length;i++){
            char[] s = strs[i].toCharArray();
            Arrays.sort(s);
            String str = new String(s);
            if(!map.containsKey(str)){
                List<String> cur = new ArrayList<>();
                cur.add(strs[i]);
                map.put(str,cur);
            }else{
                map.get(str).add(strs[i]);
            }
        }
        //这种方法更加高效, 快了7ms, 此种方法长见识了
        List<List<String>> ret = new ArrayList<>(map.values());
        return ret;
    }
}
